0673. 最长递增子序列的个数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

给定一个未排序的整数数组 nums， 返回最长递增子序列的个数。

注意 这个数列必须是 严格 递增的。

---

示例 1：

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2：

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

提示：

• 1 <= nums.length <= 2000
• -10^6 <= nums[i] <= 10^6

2. 🎯 s.1 - 动态规划

c

int findNumberOfLIS(int* nums, int numsSize) {
    int* dp = (int*)malloc(sizeof(int) * numsSize);
    int* cnt = (int*)malloc(sizeof(int) * numsSize);
    int maxLen = 1;
    for (int i = 0; i < numsSize; i++) {
        dp[i] = 1; cnt[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; cnt[i] = cnt[j]; }
                else if (dp[j] + 1 == dp[i]) cnt[i] += cnt[j];
            }
        }
        if (dp[i] > maxLen) maxLen = dp[i];
    }
    int res = 0;
    for (int i = 0; i < numsSize; i++)
        if (dp[i] == maxLen) res += cnt[i];
    free(dp); free(cnt);
    return res;
}

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumberOfLIS = function (nums) {
  const n = nums.length
  const dp = new Array(n).fill(1)
  const cnt = new Array(n).fill(1)
  let maxLen = 1
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        if (dp[j] + 1 > dp[i]) {
          dp[i] = dp[j] + 1
          cnt[i] = cnt[j]
        } else if (dp[j] + 1 === dp[i]) {
          cnt[i] += cnt[j]
        }
      }
    }
    maxLen = Math.max(maxLen, dp[i])
  }
  let res = 0
  for (let i = 0; i < n; i++) {
    if (dp[i] === maxLen) res += cnt[i]
  }
  return res
}

py

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n
        cnt = [1] * n
        max_len = 1
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        cnt[i] = cnt[j]
                    elif dp[j] + 1 == dp[i]:
                        cnt[i] += cnt[j]
            max_len = max(max_len, dp[i])
        return sum(c for d, c in zip(dp, cnt) if d == max_len)

• 时间复杂度：$O(n^2)$，其中 n 是数组长度
• 空间复杂度：$O(n)$

算法思路：

• dp[i] 表示以 nums[i] 结尾的 LIS 长度，cnt[i] 表示对应的方案数
• 若 dp[j]+1 > dp[i]，更新长度并继承方案数；若等于，累加方案数
• 最终统计所有 dp[i] == maxLen 的 cnt[i] 之和